package com.lw.leetcode.node;

/**
 * 993. 二叉树的堂兄弟节点
 */
public class IsCousins {

    int d1 = 0;
    int d2 = 0;
    int f1;
    int f2;
    public boolean isCousins(TreeNode root, int x, int y) {
        if (root.val == x || root.val == y) {
            return false;
        }
        find(root, root.left, x, y, 1);
        find(root, root.right, x, y, 1);
        return d1 == d2 && f1 != f2;
    }

    private void find(TreeNode last, TreeNode root, int x, int y, int d) {
        if (root == null) {
            return;
        }
        if (root.val == x) {
            d1 = d;
            f1 = last.val;
        }
        if (root.val == y) {
            d2 = d;
            f2 = last.val;
        }
        if (d1 != 0 && d2 != 0) {
            return;
        }
        find(root, root.left, x, y, d + 1);
        find(root, root.right, x, y, d + 1);
    }

}
